package org.example.myleet.p556;

public class Solution {
    public int nextGreaterElement(int n) {
        char[] input = (n + "").toCharArray();
        char[] output = nextPermutation(input);
        long result = Long.parseLong(new String(output));
        if (result > Integer.MAX_VALUE) {
            return -1;
        }
        int r = (int) result;
        if (r == n) {
            return -1;
        }
        return r;
    }

    /**
     * 求下一个字典序
     * @param input 输入
     * @return 对输入的拷贝，并且是input的下一个字典序，如果没有下一个字典序，则返回值顺序和input一样
     * 参考：https://www.cnblogs.com/yjxyy/p/10772963.html
     * 共3步，参考资料里面第一步是"找到最后一个正序序列ai,ai+1"，此处做了一个转换，变成从结尾开始出现的第一个降序位置，结果是一样的
     */
    private char[] nextPermutation(char[] input) {
        int n = input.length;
        //这里对input做了拷贝，操作过程不影响input
        char[] output = new char[n];
        System.arraycopy(input, 0, output, 0, n);
        if (n < 2) {
            //少于2个字符长度的没有下一个字典序可言
            return output;
        }
        //1、从字符串结尾开始向头部扫描，找到第一个出现降序的字符，满足output[j] < output[i]，标记j位置
        //解析：能找到这样的位置，说明还存在存在更大的字典序
        int j = n - 1, i = j - 1;
        while (i >= 0) {
            if (output[i] < output[j]) {
                break;
            }
            --i;
            --j;
        }
        if (i < 0) {
            //已经是最大字典序，结束
            return output;
        }
        //2、找到output[i]后面最后一个比他大的数output[j]
        //解析：output[j]是i位置之后刚刚好比output[i]大的数，这样选output[j]的原因是下一个字典序是离现在的字典序最近的
        for (int k = j; k < n; ++k) {
            if (output[i] < output[k]) {
                j = k;
            }
        }
        //3、将i和j位置的字符对调
        //解析：此时output[j]被放到i位置，这样字典序就已经比input大很多了
        char t = output[j];
        output[j] = output[i];
        output[i] = t;
        //4、最后将(i+1)位置到结尾范围的字符翻转，即可得到下一个字典序结果
        //解析：注意到output[i+1]、output[i+2]...output[n-1]的排列是单调递减的，此段范围内字典序最大，通过翻转之后可以变成最小字典序
        //以上四步完成后即可得到最接近input的下一个字典序，因为output[j]是刚刚好比output[i]大，且i位置后的序列变成最小字典序
        int l = i + 1, r = n - 1;
        while (l < r) {
            t = output[l];
            output[l] = output[r];
            output[r] = t;
            ++l;
            --r;
        }
        return output;
    }
}
